package com.huangpeng.algorithm.dataStructure;

import java.util.BitSet;

/**
 * @Author huangpeng
 * @Title 八皇后的算法
 * @Package
 * @Date 2021/7/26 14:16
 * @Description
 * @Version 1.0
 */
public class Recall {
    final static int SIZE = 8;
    int[] result = new int[SIZE];// 全局或成员变量, 下标表示行, 值表示 queen 存储在哪一列

    /**
     * 8皇后算法计算
     * @param row
     */
    public void cal8queens(int row){// 调用方式：cal8queens(0);
        if(row == SIZE){// 8 个棋子都放置好了，打印结果
            printQueens(result);
            return;// 8 行棋子都放好了，已经没法再往下递归了，所以就 return
        }
        for (int column = 0; column < SIZE; column++) {// 每一行都有 8 中放法
            if(isOk(row,column)){// 有些放法不满足要求
                result[row] = column;// 第 row 行的棋子放到了 column 列
                cal8queens(row + 1);// 考察下一行
            }
        }
    }

    /**
     * // 判断 row 行 column 列放置是否合适
     * @param row
     * @param column
     * @return
     */
    private boolean isOk(int row, int column) {
        int leftUp = column - 1;
        int rightUp = column + 1;
        for (int i = row - 1; i >= 0; i--) {// 逐行往上考察每一行
            if(result[row] == column){// 第 i 行的 column 列有棋子吗？
                return false;
            }
            if(leftUp >= 0){// 考察左上对角线：第 i 行 leftup 列有棋子吗？
                if(result[i] == leftUp){
                    return false;
                }
            }
            if(rightUp < SIZE){// 考察右上对角线：第 i 行 rightup 列有棋子吗？
                if(result[i] == rightUp){
                    return false;
                }
            }
            leftUp --;
            rightUp ++;
        }
        return true;
    }

    /**
     * // 打印出一个二维矩阵
     * @param result
     */
    private void printQueens(int[] result) {
        for (int row = 0; row < SIZE; row++) {
            for (int column  = 0; column  < SIZE; column ++) {
                if(result[row] == column){
                    System.out.print("Q ");
                }else{
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Recall recall = new Recall();
        recall.cal8queens(0);
        BitSet bitSet = new BitSet();

        int x = 3;
        System.out.println("dsadd = " + (x << 2));
    }

}
